def buil_max_heap(seq=[]):  # 构造一个堆，将堆中所有数据重新排序

    for i in range(len(seq) // 2 - 1, -1, -1):  # 从后往前出遍历(最后一个节点的父节点)  '//' 表示整除结果向下取整
        max_heap(seq, len(seq), i)  # 这里堆的大小是固定，root是i逐步减小
    return seq

def max_heap(seq, heap_size, index):
    # 调整列表中的元素以保证以index为根的堆是一个最大堆--->从而最终得到从小到大的排列顺序
    # 将当前结点与其左右子节点比较，将较大的结点与当前结点交换，然后递归地调整子树
    left_child = 2 * index + 1
    right_child = left_child + 1
    largest_index = index
    # 确定到底和左节点还是右节点换，先判断左节点
    if left_child < heap_size and seq[left_child] > seq[index]:
        largest_index = left_child
    if right_child < heap_size and seq[right_child] > seq[index]:
        largest_index = right_child
    if largest_index != index:  # 如果做了堆调整：则larger的值等于左节点或者右节点的，这个时候做对调值操作
        seq[index], seq[largest_index] = seq[largest_index], seq[index]
        max_heap(seq, heap_size, largest_index)  # 从顶端递归往下调整，用larger是因为larger是数组索引，并且已经在比较时候更新过，而root没有更新过！


def heap_sort(seq):
    buil_max_heap(seq)
    for i in range(len(seq) - 1, -1, -1):
        seq[0], seq[i] = seq[i], seq[0]
        max_heap(seq, i, 0)


seq = [38, 27, 43, 3, 9, 82, 10]

heap_sort(seq)

print('result', seq)
